package history

import "strconv"

func Solution(A []int, B []int, N int) int {
	// Implement your solution here
	var mapAtoB = make(map[int][]int)
	var mapBtoA = make(map[int][]int)
	for i := 0; i < len(A); i++ {
		mapAtoB[A[i]] = append(mapAtoB[A[i]], B[i])
		mapBtoA[B[i]] = append(mapBtoA[B[i]], A[i])
	}
	var maxCities = 0
	for i := 0; i < len(A); i++ {
		if len(mapAtoB[A[i]]) > 0 {
			var cityQueue = append(mapAtoB[A[i]], mapBtoA[B[i]]...)
			delete(mapAtoB, A[i])
			delete(mapBtoA, B[i])
			var cityMap = make(map[string]bool)
			var curCityRoad = 1
			for len(cityQueue) > 0 {
				var size = len(cityQueue)
				for j := 0; j < size; j++ {
					if len(mapAtoB[cityQueue[j]]) > 0 {
						var nums = mapAtoB[cityQueue[j]]
						for k := 0; k < len(nums); k++ {
							var key = strconv.Itoa(getMin(cityQueue[j], nums[k])) + "-" + strconv.Itoa(getMax(cityQueue[j], nums[k]))
							if !cityMap[key] {
								curCityRoad++
								cityMap[key] = true
							}
						}
						cityQueue = append(cityQueue, mapAtoB[cityQueue[j]]...)
						delete(mapAtoB, cityQueue[j])
					}
					if len(mapBtoA[cityQueue[j]]) > 0 {
						var nums = mapBtoA[cityQueue[j]]
						for k := 0; k < len(nums); k++ {
							var key = strconv.Itoa(getMin(cityQueue[j], nums[k])) + "-" + strconv.Itoa(getMax(cityQueue[j], nums[k]))
							if !cityMap[key] {
								curCityRoad++
								cityMap[key] = true
							}
						}
						cityQueue = append(cityQueue, mapBtoA[cityQueue[j]]...)
						delete(mapBtoA, cityQueue[j])
					}

				}
				cityQueue = cityQueue[size:]
			}
			if curCityRoad > maxCities {
				maxCities = curCityRoad
			}
		}

	}
	return maxCities
}

func getMax(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func getMin(a, b int) int {
	if a < b {
		return a
	}
	return b
}
